package com.gxc.rapacity;

/**
 * N皇后问题是指在N*N的棋盘上要摆N个皇后，
 * 要求任何两个皇后不同行、不同列也不在同一条斜线上。
 * 给定一个整数n，返回n皇后的摆法有多少种。n=1，返回1。
 * n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0。
 * n=8，返回92。
 *
 * 暴力递归
 */
public class NQueen {

    public static void main(String[] args) {
        int num = 8;

        int result = nQueen(num);
        System.out.println(result);

        result = nQueenOptimize(num);
        System.out.println(result);
    }

    //优化版N皇后
    private static int nQueenOptimize(int num) {
        if (num<1 || num>32) return 0;

        //用二进制表示皇后的数量
        int limit = num==32?-1:(1<<num)-1;
        return processOptimize(limit, 0, 0, 0);
    }


    /**
     *
     * @param limit  皇后的所有的位置
     * @param colLim  列的限制，1的位置不能放皇后，0的位置可放
     * @param leftDataLim  左斜线的限制，1的位置不能放皇后，0的位置可放
     * @param rightDataLim  右斜线的限制，1的位置不能放皇后，0的位置可放
     * @return
     */
    private static int processOptimize(int limit, int colLim, int leftDataLim, int rightDataLim) {
        if (limit == colLim) return 1;

        int result = 0;
        int noPos = colLim | leftDataLim | rightDataLim;
        //皇后的所有的可选位置，过滤已选的列和斜线，就是当前可选择的皇后位置
        int pos = limit & ~ noPos;
        //取最右边的1
        int mostRighrOne = 0;
        while (pos!=0) {
            mostRighrOne = pos & (~pos+1); //取最右边的1
            pos = pos - mostRighrOne;
            result += processOptimize(limit, colLim|mostRighrOne,
                    (leftDataLim|mostRighrOne)<<1,
                    (rightDataLim|mostRighrOne)>>1);
        }

        return result;
    }

    //用数组记录已选皇后的位置
    private static int nQueen(int num) {
        if (num<1) return 0;

        //i行的皇后放在第几列
        int[] record = new int[num];
        return process(0, num, record);
    }

    /**
     *
     * @param i  第I行
     * @param num   总共多少行
     * @param record   已选中的皇后的位置
     */
    private static int process(int i, int num, int[] record) {
        //当i来到num行，标识找到一种排列方式
        if ( i== num) return 1;

        //总次数
        int result = 0;
        //皇后的位置处于第i行第j列
        for (int j = 0; j < num; j++) {
            //第i行第j列的皇后是否和已选中的重复
            if (isValid(i, j, record)) {
                record[i] = j;
                result += process(i+1, num, record);
            }
        }
        return result;
    }

    /**
     * 判断皇后位置是否符合条件
     * @param i 皇后处于i行
     * @param j 皇后处于J列
     * @param record  已选中的皇后的位置
     * @return
     */
    private static boolean isValid(int i, int j, int[] record) {
        for (int i1 = 0; i1 < i; i1++) {
            if (Math.abs(i1-i) == Math.abs(record[i1]-j) || i==i1 || j==record[i1]) return false;
        }
        return true;
    }
}
